{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check if a Parentheses String Can Be Valid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canBeValid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #判断一个括号字符串是否有效"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个括号字符串是只由&nbsp;<code>'('</code> 和&nbsp;<code>')'</code>&nbsp;组成的&nbsp;<strong>非空</strong>&nbsp;字符串。如果一个字符串满足下面 <b>任意</b>&nbsp;一个条件，那么它就是有效的：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>字符串为&nbsp;<code>()</code>.</li>\n",
    "\t<li>它可以表示为 <code>AB</code><span style=\"\">（</span><code>A</code>&nbsp;与&nbsp;<code>B</code>&nbsp;连接），其中<code>A</code> 和&nbsp;<code>B</code>&nbsp;都是有效括号字符串。</li>\n",
    "\t<li>它可以表示为&nbsp;<code>(A)</code>&nbsp;，其中&nbsp;<code>A</code>&nbsp;是一个有效括号字符串。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个括号字符串&nbsp;<code>s</code>&nbsp;和一个字符串&nbsp;<code>locked</code>&nbsp;，两者长度都为&nbsp;<code>n</code>&nbsp;。<code>locked</code>&nbsp;是一个二进制字符串，只包含&nbsp;<code>'0'</code>&nbsp;和&nbsp;<code>'1'</code>&nbsp;。对于&nbsp;<code>locked</code>&nbsp;中&nbsp;<strong>每一个</strong>&nbsp;下标&nbsp;<code>i</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果&nbsp;<code>locked[i]</code>&nbsp;是&nbsp;<code>'1'</code>&nbsp;，你 <strong>不能</strong>&nbsp;改变&nbsp;<code>s[i]</code>&nbsp;。</li>\n",
    "\t<li>如果&nbsp;<code>locked[i]</code>&nbsp;是&nbsp;<code>'0'</code>&nbsp;，你&nbsp;<strong>可以</strong>&nbsp;将&nbsp;<code>s[i]</code>&nbsp;变为&nbsp;<code>'('</code>&nbsp;或者&nbsp;<code>')'</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果你可以将 <code>s</code>&nbsp;变为有效括号字符串，请你返回&nbsp;<code>true</code>&nbsp;，否则返回&nbsp;<code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/11/06/eg1.png\" style=\"width: 311px; height: 101px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"))()))\", locked = \"010100\"\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>locked[1] == '1' 和 locked[3] == '1' ，所以我们无法改变 s[1] 或者 s[3] 。\n",
    "我们可以将 s[0] 和 s[4] 变为 '(' ，不改变 s[2] 和 s[5] ，使 s 变为有效字符串。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"()()\", locked = \"0000\"\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>我们不需要做任何改变，因为 s 已经是有效字符串了。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \")\", locked = \"0\"\n",
    "<b>输出：</b>false\n",
    "<b>解释：</b>locked 允许改变 s[0] 。\n",
    "但无论将 s[0] 变为 '(' 或者 ')' 都无法使 s 变为有效字符串。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == s.length == locked.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s[i]</code>&nbsp;要么是&nbsp;<code>'('</code>&nbsp;要么是&nbsp;<code>')'</code>&nbsp;。</li>\n",
    "\t<li><code>locked[i]</code> 要么是&nbsp;<code>'0'</code>&nbsp;要么是&nbsp;<code>'1'</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-if-a-parentheses-string-can-be-valid](https://leetcode.cn/problems/check-if-a-parentheses-string-can-be-valid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-if-a-parentheses-string-can-be-valid](https://leetcode.cn/problems/check-if-a-parentheses-string-can-be-valid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"))()))\"\\n\"010100\"', '\"()()\"\\n\"0000\"', '\")\"\\n\"0\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canBeValid(self, s: str, locked: str) -> bool: \n",
    "        if len(s)&1:\n",
    "            return False\n",
    "        a=0\n",
    "        for it1,it2 in zip(s,locked):\n",
    "            if it2=='1':\n",
    "                if it1==')':\n",
    "                    if a==0:\n",
    "                        return False\n",
    "                    else:\n",
    "                        a-=1\n",
    "                else:\n",
    "                    a+=1\n",
    "            else:\n",
    "                a+=1\n",
    "        a=0\n",
    "        for it1,it2 in zip(reversed(s),reversed(locked)):\n",
    "            if it2=='1':\n",
    "                if it1=='(':\n",
    "                    if a==0:\n",
    "                        return False\n",
    "                    else:\n",
    "                        a-=1\n",
    "                else:\n",
    "                    a+=1\n",
    "            else:\n",
    "                a+=1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canBeValid(self, s: str, locked: str) -> bool:\n",
    "        n = len(s)\n",
    "        if n & 1:\n",
    "            return False\n",
    "        free = l = 0\n",
    "        # 判断右括号能否处理掉\n",
    "        for i in range(n):\n",
    "            if locked[i] == '0': free += 1\n",
    "            else:\n",
    "                if s[i] == '(': l += 1\n",
    "                else:\n",
    "                    if l != 0:\n",
    "                        l -= 1\n",
    "                    elif free != 0:\n",
    "                        free -= 1\n",
    "                    else:\n",
    "                        return False\n",
    "        # 判断左括号能否处理掉\n",
    "        free = r = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if locked[i] == '0': free += 1\n",
    "            else:\n",
    "                if s[i] == ')': r += 1\n",
    "                else:\n",
    "                    if r != 0:\n",
    "                        r -= 1\n",
    "                    elif free != 0:\n",
    "                        free -= 1\n",
    "                    else:\n",
    "                        return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canBeValid(self, s: str, locked: str) -> bool:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        if (n % 2) == 1:\n",
    "            return False\n",
    "        mx = mn = 0\n",
    "        for i in range(n):\n",
    "            if locked[i] == '0':\n",
    "                mx += 1\n",
    "                if mn > 0:\n",
    "                    mn -= 1\n",
    "            if locked[i] == '1' and s[i] == '(':\n",
    "                mx += 1\n",
    "                mn += 1\n",
    "            if locked[i] == '1' and s[i] == ')':\n",
    "                mx -= 1\n",
    "                if mn > 0:\n",
    "                    mn -= 1\n",
    "            if mx < mn:\n",
    "                return False\n",
    "        return mn == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canBeValid(self, s: str, locked: str) -> bool:\n",
    "        if len(s) % 2 != 0:\n",
    "            return False\n",
    "        x = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '(' or locked[i] == '0':\n",
    "                x += 1\n",
    "            elif x > 0:\n",
    "                x -= 1\n",
    "            else:\n",
    "                return False\n",
    "        x = 0\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "            c = s[i]\n",
    "            if c == ')' or locked[i] == '0':\n",
    "                x += 1\n",
    "            elif x > 0:\n",
    "                x -= 1\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canBeValid(self, s: str, locked: str) -> bool:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        if (n % 2) == 1:\n",
    "            return False\n",
    "        mx = mn = 0\n",
    "        for i in range(n):\n",
    "            if locked[i] == '0':\n",
    "                mx += 1\n",
    "                if mn > 0:\n",
    "                    mn -= 1\n",
    "            if locked[i] == '1' and s[i] == '(':\n",
    "                mx += 1\n",
    "                mn += 1\n",
    "            if locked[i] == '1' and s[i] == ')':\n",
    "                mx -= 1\n",
    "                if mn > 0:\n",
    "                    mn -= 1\n",
    "            if mx < mn:\n",
    "                return False\n",
    "        return mn == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canBeValid(self, s: str, locked: str) -> bool:  \n",
    "        left = 0\n",
    "        right = 0\n",
    "        if len(s) % 2==1:return False\n",
    "        for i in range(len(s)):\n",
    "            if locked[i] == '1' and s[i] == ')':\n",
    "                left += 1\n",
    "                if left > (i+1)//2:\n",
    "                    return False\n",
    "            j = len(s) - 1 - i\n",
    "            if locked[j] == '1' and s[j] == '(':\n",
    "                right += 1\n",
    "                if right > (len(s)-j) // 2:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canBeValid(self, s: str, locked: str) -> bool:\n",
    "        if len(s)%2!=0:\n",
    "            return False\n",
    "        if s[0]==\")\" and locked[0]==\"1\":\n",
    "            return False\n",
    "        if s[-1]==\"(\" and locked[-1]==\"1\":\n",
    "            return False\n",
    "        left = 0\n",
    "        right = 0\n",
    "        tmp = 0\n",
    "        for i in range(len(s)):\n",
    "            if left+tmp<right:\n",
    "                print(left,tmp,right)\n",
    "                return False\n",
    "            if locked[i]==\"0\":\n",
    "                tmp+=1\n",
    "                continue\n",
    "            if s[i]==\"(\":\n",
    "                left+=1\n",
    "                continue\n",
    "            right+=1\n",
    "        left = 0\n",
    "        right = 0\n",
    "        tmp = 0\n",
    "        for i in range(len(s)):\n",
    "            if left+tmp<right:\n",
    "                print(\"sec\")\n",
    "                print(left,tmp,right)\n",
    "                return False\n",
    "            if locked[-i-1]==\"0\":\n",
    "                tmp+=1\n",
    "                continue\n",
    "            if s[-i-1]==\")\":\n",
    "                left+=1\n",
    "                continue\n",
    "            right+=1\n",
    "        print(left,tmp,right)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canBeValid(self, s: str, locked: str) -> bool:\n",
    "        if len(s)%2 == 1:\n",
    "            return False\n",
    "        \n",
    "        # 未匹配的左括号的最大、最小值\n",
    "        max_left = min_left = 0\n",
    "        for ch, b in zip(s, locked):\n",
    "            \n",
    "            # locked[i]==1时，无法改变字符，直接加减\n",
    "            if ch == '(' and b == '1':\n",
    "                max_left += 1\n",
    "                min_left += 1\n",
    "            elif ch == ')' and b == '1':\n",
    "                max_left -= 1\n",
    "                min_left -= 1\n",
    "            \n",
    "            # locked[i]==0时，可作为通配符，\n",
    "            # 贪心地将：未匹配的左括号的最大值+1、最小值-1\n",
    "            elif b == '0':\n",
    "                max_left += 1\n",
    "                min_left -= 1\n",
    "            \n",
    "            # 保持当前未匹配的左括号的最小值>=0，这样才合法\n",
    "            min_left = max(0, min_left)\n",
    "\n",
    "            # 未匹配的左括号的最大值不能小于其最小值，否则不合法\n",
    "            if max_left < min_left:\n",
    "                return False\n",
    "        \n",
    "        return min_left == 0    # 最终未匹配的左括号的最小值应为0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canBeValid(self, s: str, locked: str) -> bool:\n",
    "        n = len(s)\n",
    "        if n % 2:return False\n",
    "        temp = 0;cnt = 0\n",
    "        for i in range(n):\n",
    "            if locked[i] == '1':\n",
    "                temp += 1 if s[i] == '(' else -1\n",
    "            else:\n",
    "                cnt += 1\n",
    "            if temp + cnt < 0:return False\n",
    "        temp = 0;cnt = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if locked[i] == '1':\n",
    "                temp += 1 if s[i] == ')' else -1\n",
    "            else:\n",
    "                cnt += 1\n",
    "            if temp + cnt < 0:return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canBeValid(self, s: str, locked: str) -> bool:\n",
    "        if len(s) % 2 == 1: return False\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '(' or locked[i] == '0': ans += 1\n",
    "            else:\n",
    "                if ans > 0: ans -=1\n",
    "                else: return False\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "            if s[i] == ')' or locked[i] == '0': ans += 1\n",
    "            else:\n",
    "                if ans > 0: ans -= 1\n",
    "                else: return False       \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canBeValid(self, s: str, locked: str) -> bool:\n",
    "      if len(s) % 2:  return False\n",
    "      chr2num = {\"(\": 1, \")\": -1}\n",
    "\n",
    "      L = R = 0\n",
    "      for ch, flag in zip(s, locked):\n",
    "        if flag == \"1\":\n",
    "          L += chr2num[ch]\n",
    "          R += chr2num[ch]\n",
    "          if L == -1: L = 1\n",
    "          if R < 0:  return False\n",
    "        else:\n",
    "          L -= 1\n",
    "          R += 1\n",
    "          if L == -1: L = 1\n",
    "      return L <= 0 <= R    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canBeValid(self, s: str, locked: str) -> bool:\n",
    "        n, p, q = len(s), 0, 0\n",
    "        if n % 2: return False\n",
    "        for i,j in zip(s, locked):\n",
    "            if j=='0': p, q = (1 if p == 0 else p - 1), q + 1\n",
    "            elif i=='(': p, q = p + 1, q + 1\n",
    "            else:\n",
    "                p, q = (1 if p == 0 else p - 1), q - 1\n",
    "                if q < 0: return False\n",
    "        return p == 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canBeValid(self, s: str, locked: str) -> bool:\n",
    "        n = len(s)\n",
    "        mx = 0   # 可以达到的最大分数\n",
    "        mn = 0   # 可以达到的最小分数 与 最小有效前缀对应分数 的较大值\n",
    "        for i in range(n):\n",
    "            if locked[i] == '1':\n",
    "                # 此时对应字符无法更改\n",
    "                if s[i] == '(':\n",
    "                    diff = 1\n",
    "                else:\n",
    "                    diff = -1\n",
    "                mx += diff\n",
    "                mn = max(mn + diff, (i + 1) % 2)\n",
    "            else:\n",
    "                # 此时对应字符可以更改\n",
    "                mx += 1\n",
    "                mn = max(mn - 1, (i + 1) % 2)\n",
    "            if mx < mn:\n",
    "                # 此时该前缀无法变为有效前缀\n",
    "                return False\n",
    "        # 最终确定 s 能否通过变换使得分数为 0（成为有效字符串）\n",
    "        return mn == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canBeValid(self, s: str, locked: str) -> bool:\n",
    "        if len(s)%2==1:\n",
    "            return False\n",
    "        maxleft, minleft = 0,0\n",
    "        for v,i in zip(s,locked):\n",
    "            if v == '(' and i=='1':\n",
    "                maxleft += 1\n",
    "                minleft += 1\n",
    "            elif v==')' and i=='1':\n",
    "                maxleft -= 1\n",
    "                minleft -= 1\n",
    "            elif i=='0':\n",
    "                maxleft += 1\n",
    "                minleft -= 1\n",
    "            minleft = max(0,minleft)\n",
    "            if minleft>maxleft:\n",
    "                return False        \n",
    "        return minleft == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canBeValid(self, s: str, locked: str) -> bool:\n",
    "        n1 = 0\n",
    "        n2 = 0\n",
    "        n = len(s)\n",
    "        if n % 2 == 1:\n",
    "            return False\n",
    "        for i in range(n):\n",
    "            if locked[i] == '1':\n",
    "                if s[i] == '(':\n",
    "                    n1 += 1\n",
    "                    n2 += 1\n",
    "                else:\n",
    "                    n1 -= 1\n",
    "                    if n2 > 0:\n",
    "                        n2 -= 1\n",
    "            else:\n",
    "                n1 += 1\n",
    "                if n2 > 0:\n",
    "                    n2 -= 1\n",
    "            if n1 < 0:\n",
    "                return False\n",
    "        return n2 == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canBeValid(self, s: str, locked: str) -> bool:\n",
    "        if len(s) % 2 != 0:\n",
    "            return False\n",
    "        if (s[0] == ')' and locked[0] == '1') or (s[-1] == '(' and locked[-1] == '1'):\n",
    "            return False\n",
    "        left, right = 1, 0\n",
    "        rd = 0\n",
    "        for i, x in enumerate(s[1:]):\n",
    "            if x == ')':\n",
    "                if locked[i+1] == '0':\n",
    "                    rd += 1\n",
    "                else:\n",
    "                    right += 1\n",
    "            else:\n",
    "                if locked[i+1] == '0':\n",
    "                    rd += 1\n",
    "                else:\n",
    "                    left += 1\n",
    "            if right - left > rd:\n",
    "                return False\n",
    "        flag = abs(left - right) <= rd\n",
    "        left, right = 0, 1\n",
    "        rd = 0\n",
    "        for i in range(len(s) - 2, -1, -1):\n",
    "            if s[i] == '(':\n",
    "                if locked[i] == '0':\n",
    "                    rd += 1\n",
    "                else:\n",
    "                    left += 1\n",
    "            else:\n",
    "                if locked[i] == '0':\n",
    "                    rd += 1\n",
    "                else:\n",
    "                    right += 1\n",
    "            if left - right > rd:\n",
    "                return False\n",
    "        return flag and abs(left - right) <= rd\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canBeValid(self, s: str, locked: str) -> bool:\n",
    "        mi = ma = 0\n",
    "        n = len(s)\n",
    "        if n & 1:\n",
    "            return False\n",
    "        def go(s, locked, c):\n",
    "            left = right = 0\n",
    "            every = 0\n",
    "            for i in range(n):\n",
    "                if locked[i] == '0':\n",
    "                    every += 1\n",
    "                else:\n",
    "                    if s[i] == c:\n",
    "                        left += 1\n",
    "                    else:\n",
    "                        right += 1\n",
    "                        if right > left + every:\n",
    "                            return False\n",
    "            return abs(right - left) <= every\n",
    "        return go(s, locked, '(') and go(s[::-1], locked[::-1], ')')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canBeValid(self, s: str, locked: str) -> bool:\n",
    "        m, n = len(s), len(locked)\n",
    "        if m != n or m & 1: return False\n",
    "\n",
    "        def check(s: str, locked: str, parenthesis: int) -> bool:\n",
    "            count = 0\n",
    "            l = len(s)\n",
    "            for i in range(l):\n",
    "                if locked[i] == '1':\n",
    "                    if s[i] == parenthesis:\n",
    "                        count += 1\n",
    "                    else :\n",
    "                        count -= 1\n",
    "                        if count < 0:   return False\n",
    "                # for unlocked case, increment count to avoid it go below 0\n",
    "                elif locked[i] == '0':\n",
    "                    count += 1\n",
    "            return True\n",
    "        \n",
    "        return check(s, locked, '(') and check(s[::-1], locked[::-1], ')')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canBeValid(self, s: str, locked: str) -> bool:\n",
    "        n = len(s)\n",
    "        if n % 2: return False\n",
    "        left, free = [], []\n",
    "        for i in range(n):\n",
    "            # 如果是0, 则是可变\n",
    "            if locked[i] == '0':\n",
    "                free.append(i)\n",
    "            # 如果是1, 则需要匹配\n",
    "            else:\n",
    "                # 如果是不可变), 看左边能否匹配\n",
    "                if s[i] == ')':\n",
    "                    # 存在(能匹配, 则匹配\n",
    "                    if left:\n",
    "                        left.pop()\n",
    "                    # 若不能匹配, 则用可变匹配\n",
    "                    elif free:\n",
    "                        free.pop()\n",
    "                    # 否则)左边没有可以与之匹配的\n",
    "                    else:\n",
    "                        return False\n",
    "                # 如果是不可变的(, 则加入左边记录栈, 用于后续匹配\n",
    "                else:\n",
    "                    left.append(i)\n",
    "        # 如果左边记录栈不为空, 则表明需要在右边寻找匹配\n",
    "        while left:\n",
    "            # 如果已经没了可变 or 可变不在(的右边\n",
    "            if not free or free[-1] < left[-1]:\n",
    "                # 那么无法匹配\n",
    "                return False\n",
    "            # 除开上述情况, 就是可匹配\n",
    "            free.pop()\n",
    "            left.pop()\n",
    "        # 最后判定(是否匹配完了\n",
    "        return len(left) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canBeValid(self, s: str, locked: str) -> bool:\n",
    "        slen  = len(s)  \n",
    "        if slen %2: return False \n",
    "        free,lock = list(),list()  \n",
    "        for i in range(slen):\n",
    "            if locked[i]!=\"1\":\n",
    "                free.append(i)  \n",
    "            else:\n",
    "                if s[i] ==')':\n",
    "                    if lock:\n",
    "                        lock.pop()  \n",
    "                    elif free: free.pop()  \n",
    "                    else:\n",
    "                        return False \n",
    "                elif s[i] =='(':\n",
    "                    lock.append(i)   \n",
    "        while free and lock:\n",
    "            if free[-1]<lock[-1]:\n",
    "                return False \n",
    "            free.pop()\n",
    "            lock.pop() \n",
    "        return len(lock) ==0 "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
